import java.util.ArrayList;
import java.util.List;
//118 - 杨辉三角
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> row = new ArrayList<>();
        row.add(1);//第一行为1
        ret.add(row);//把第一行放进去
        for (int i = 1; i < numRows; i++) {//从第二行开始
            List<Integer> cur = new ArrayList<>();//第 i 行所存放的数据
            cur.add(1);//第一个是1
            for (int j = 1; j < i; j++) {
                int x = ret.get(i-1).get(j) + ret.get(i-1).get(j-1);//[i][j] = [i-1][j]+[i-1][j-1]
                cur.add(x);//中间值存放
            }
            cur.add(1);//最后一个也是1
            ret.add(cur);//将这一行放入ret
        }
        return ret;
    }
}
//27 - 移除元素
class Solution1 {
    public int removeElement(int[] nums, int val) {
        int i = 0,j = 0;
        for(;j<nums.length;j++){
            if(nums[j] != val){
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}
//26 - 删除有序数组中的重复数字
class Solution3 {
    public int removeDuplicates(int[] nums) {
        int i = 1;
        int j = 1;
        for(;j<nums.length;j++){
            if(nums[j]!=nums[j-1]){
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}
//88 合并两个有序数组
class Solution4 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while(i>=0&&j>=0){

            if(nums1[i]>nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        while(i==-1&&j>=0){
            nums1[k--] = nums2[j--];
        }
        while(j==-1&&i>=0){
            nums1[k--] = nums1[i--];
        }

    }
}
public class Test {

}
